/*
 * @lc app=leetcode.cn id=474 lang=java
 *
 * [474] 一和零
 */

// @lc code=start
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //两个维度的01背包
        int[][] dp=new int[m+1][n+1];
        for(String s:strs){//遍历物品
            int zeroBag=0,oneBag=0;
            for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='0'){
                    zeroBag++;
                }else{
                    oneBag++;
                }
            }

            for(int i=m;i>=zeroBag;i--){
                for(int j=n;j>=oneBag;j--){
                    dp[i][j]=Math.max(dp[i][j], dp[i-zeroBag][j-oneBag]+1);
                }
            }

        }
        return dp[m][n];
    }
}
// @lc code=end

